The transmission of images containing gray scale information using existing facsimile equipment has been the subject of considerable research. There are many techniques for transforming a multilevel gray scale image to a binary approximation of that image. Dither coding and superpel coding are two of the most effective and most widely used techniques for accomplishing this. Superpel coding employs an n .times. n matrix of bilevel pixels to approximate each multilevel gray scale pixel in the image. Dither coding employs one or more thresholds and each multilevel gray scale pixel in the image is compared to one of the thresholds to produce a single bilevel pixel.
The principal advantage of dither coding as compared with superpel coding is that a dithered image realizes an N to 1 reduction in information over the N bit gray scale image, while an image produced by superpel coding realizes an (n .times. n) to N information expansion (where n.gtoreq. 3).
There are several dither coding techniques available, including random dithering, clumped dithering, and ordered dithering. In random dithering, each multilevel gray scale pixel is compared with a threshold selected randomly from the dynamic range of the image. Ordered dithering employs a rectangular matrix of fixed thresholds; each multilevel gray scale pixel in the image is compared to one of the thresholds in the rectangular matrix. The thresholds are arranged in the matrix so as to produce a set of pseudo-gray levels by varying the ratio of black to white pixels in the matrix.
Clumped dithering is an electronic approximation of the photomechanical screening process and employs an irregularly shaped matrix of fixed thresholds. The thresholds are arranged so that a "dot" grows outward from the center of the matrix as successively darker shades of gray are encountered in the image. Clumped dithering produced dithered images that, in general, contain more contrast and better pseudo-gray scale rendition than images produced by either random or ordered dithering.
There are several drawbacks to employing dither coding for transmitting gray scale images using existing facsimile equipment. A dithered image contains a large amount of short black and white pixel runs, and this limits the effectiveness of the Modified Huffman and Modified READ compression techniques employed in typical facsimile machines. Further, dither coding of images containing an appreciable amount of high contrast information (e.g., text) causes severe distortion of the high contrast information in the dithered image.
Patents of interest in this field include the following U.S. Pat. Nos. 3,967,052 (Judice); 4,549,220 (Suzuki); 4,593,325 (Kannapell et al); 4,606,069 (Johnson); 4,468,704 (Stoffel et al); 4,631,521 (El-Sherbini); 4,651,287 (Tsao); 4,663,662 (Sekizawa et al); 4,675,831 (Ito et al); 4,766,499 (Inazuka); 4,782,400 (Ohtani); and 4,783,841 (Crayson). Briefly considering these references, the Judice patent discloses an image transmission method which processes a gray scale image by scanning every fourth pixel along a scan line, thresholding the scanned pixels using one of the thresholds in a 4.times.4 matrix of thresholds, and placing the resulting dithered quarter-scan line in the output stream. The second quarter-scan line begins at the second pixel in the scan line, and the next threshold in the dither matrix (along the matrix row) is used to threshold the gray scale pixels. This processing continues until the entire scan line has been processed. The next scan line uses the next row in the dither matrix, and after every fourth scan line the matrix is repeated.
The Stoffel et al patent discloses an adaptive thresholder which employs a single threshold that is modified as each pixel in the image is processed. The system does not distinguish between bi-level and gray scale image content.
The Suzuki patent discloses a technique for processing image data into binary data wherein a gray scale image is processed by comparing the analog input signal to a predetermined reference o voltage and to an operator-supplied threshold command signal to select between a fixed or dither thresholding scheme. This method distinguishes between gray scale and bi-level information, but does so on a per pixel basis. Further, this technique does not take into account the local spatial characteristics of the image.
The Kannapell et al patent discloses an adaptive thresholding algorithm which processes a gray scale image in 216 pixel segments along each scan line. From each segment, a background threshold, a print threshold, and a contrast threshold are first determined. From these thresholds an estimated threshold is calculated. From neighboring segment adaptive threshold values an average threshold value for the current segment is determined. The adaptive threshold value for the current segment is then derived from the difference between the average and estimated thresholds.
The El-Sherbini patent discloses a differential run-length coding method which employs an 8.times.8 ordered dither threshold matrix to binarize the image, regardless of image content, and a reference byte differentiation technique to increase the compressibility of the dithered image. The byte differentiation technique selects a reference byte on each scan line and performs an exclusive-OR operation with the reference byte and each byte in the scan line. This method increases the length of the black and white pixel run lengths in the dithered image.
The Tsao patent discloses a digital image processing algorithm which involves reproducing continuous tone images on output devices with lower or discrete dynamic ranges by converting the local input image densities into output device densities (using a tone reproduction curve) and then performing an iterative local error minimization calculation on n.times.n block of pixels. This algorithm does not distinguish between bi-level and gray scale information.
The Sckizawa et al patent discloses a picture signal processing system employing an algorithm which provides for switching between a single binarization step and a dither binarization step. More particularly, the algorithm employs a sum-of-products convolution performed on 5.times.5 blocks of picture elements to determine the local "density" of the picture which, in turn, is used to switch between a single threshold binarization step and a 4.times.4 ordered dither threshold matrix binarization step.
The Ito et al patent discloses a method for processing gradation information which employs a group of 8.times.8 matrices of thresholds and adaptively generated gradation statistics to process an image. The disclosed method does not distinguish between bi-level and gray scale image content and is not concerned with improvement of the compression of the dithered image.
The Inazuka patent discloses a dither signal encoder-decoder system which is designed to improve compression performance, and employs a predictive technique to produce a transposition signal with a higher run length coding efficiency than the original dither signal.
The Ohtani patent discloses an analog video signal encoder-decoder system which employs a simple n x n matrix of thresholds to process an image and does not distinguish between bi-level and gray scale image content. The system increases the run-length coding efficiency of the resulting thresholded (dithered) image by converting the dithered data, which typically consists of short runs of black and white pixels, into a binary stream with longer runs of black and white pixels using an exclusive OR operation on each n-1 pixels.
The Johnson and Caryson patents disclose data compression techniques of general interest and are not concerned with dither coding.